Singly Linked Nodes | Data Structure | Pusan National University

노드(node)값과 다음 노드의 참조를 함께 저장한다.

머리(head)목록 객체가 첫 노드를 가리키는 참조다. 첫 원소 자체가 아니다.

꼬리(tail)목록 객체가 마지막 노드를 가리키는 참조다. 그 노드의 next는 None이다.

배열은 옆 칸이, 연결리스트는 next가 순서를 정한다

같은 원소 A, B, C를 두 표현에 담고 끝에 추가하는 원소 수를 바꾼다. 배열은 만들 때 용량 4칸을 한 번에 확보하고, 연결리스트는 추가할 때마다 노드를 하나 만든다.

끝에 추가한 원소 수 0

초록 칸과 노드는 방금 추가한 원소다. 점선 칸은 확보했지만 아직 쓰지 않은 배열 칸이다.

u, u.data, u.next는 각각 노드 객체, 저장값, 다음 노드의 참조를 뜻한다.

강조할 표현식

u→노드 A

data 7next → B

→

data 12next → None

→None

마지막 노드의 next가 None이면 연결이 끝난다. Python에서는 first = Node(7), second = Node(12) 뒤 first.next = second가 이 순서를 만든다.

빈 목록, 원소 하나, 원소 세 개의 상태를 바꾸고 노드의 물리적 배치를 달리해도 next가 만든 논리 순서는 유지된다.

목록 상태

노드 배치

head

tail

선은 next 참조를 나타낸다. 화면에서 가까운 노드가 다음 원소라는 뜻은 아니다.